package algorithms.sort.nlogn;

import algorithms.sort.SortingVisualization;

/**
 * 归并排序
 */
public class MergeSort extends SortingVisualization {

    /**
     * 初始化窗口大小并
     *
     * @param array
     */
    public MergeSort(int[] array) {
        super(array);
    }

    @Override
    public void showSortingProcess() {
        mergeSortHelper(0, array.length - 1);
    }


    private void mergeSortHelper(int low, int high) {
        if (low < high) {
            int mid = low + (high - low) / 2;
            mergeSortHelper(low, mid);       // 对左半部分进行归并排序
            mergeSortHelper(mid + 1, high);  // 对右半部分进行归并排序
            merge(low, mid, high);           // 合并两个有序数组
            sortPanelRepaint();
        }
    }

    private void merge(int low, int mid, int high) {
        int[] temp = new int[array.length];
        int i = low;
        int j = mid + 1;
        int k = low;

        // 合并两个有序数组到临时数组中
        while (i <= mid && j <= high) {
            if (array[i] <= array[j]) {
                temp[k] = array[i];
                i++;
            } else {
                temp[k] = array[j];
                j++;
            }
            k++;
        }

        // 复制剩余元素到临时数组中
        while (i <= mid) {
            temp[k] = array[i];
            i++;
            k++;
        }
        while (j <= high) {
            temp[k] = array[j];
            j++;
            k++;
        }

        // 将临时数组中的元素复制回原数组
        for (int m = low; m <= high; m++) {
            array[m] = temp[m];
            sortPanelRepaint();
        }
    }
}
